package leetcode_21_40;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.IntStream;

public class combinationSum2_40 {
    /**
     * candidates 中的每个数字在每个组合中只能使用 一次 。
     * 注意：解集不能包含重复的组合。
     * <p>
     * 1,2,3,4,5,6   target=6
     * 6  ->  减去自身，末尾无元素 ，判断6
     * 5  ->  减去自身，递归找到6，判断5和6
     * 4  ->  减去自身，递归找到最后的6，判断4和6，再回退到5，判断4，5，6
     *
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> combine = new ArrayList<Integer>();
        dfs(candidates, target, ans, combine, 0);
        return ans;
    }

    public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int begin) {
        if (target == 0) {  //当目标值被减到0，说明为一组匹配集合
            ans.add(new ArrayList<Integer>(combine));
            return;
        }
        //循环嵌套递归
        for (int i=begin; i<candidates.length; i++) {
            if (i > begin && candidates[i] == candidates[i - 1]) {
                //防止重复并且是和前一个比较，这样目前元素就不用判断了
                //如 1 1 2 4  会判断 1 2 4 ，1 1 4，1 1 2
                //如果是与后一个比较
                //只会判断 1 2 4，
                continue;
            }
            // 选择当前数
            if (target - candidates[i] >= 0) { //可以继续增加元素
                combine.add(candidates[i]);                   //直接添加元素，达到任意集合都去验证
                dfs(candidates, target - candidates[i], ans, combine, i + 1);  //沿用当前元素进行判断
                combine.remove(combine.size() - 1);  //递归层层回退，顺便去除其中的元素
            }
        }
    }
}
